package BinaryTree.栈遍历;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 7.18：
 *      思路：
 *         一直左到N -> pt右1 -> 右1的左
 *         ↑ loop       ←         ↓
 *      背:
 *          pop (前后push) res (中push）
 *
 *
 * 压栈正常
 *
 * 区别在：shouldJudge，
 *      节点回溯回父节点前，cur无右，shouldJudge就不会更新，保留上次的，
 *      这样就可以继续弹出栈（乱栈，靠shouldJudge维护着！）
 */
public class 二叉树的中序遍历94 {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return res;
        }
        //0 初根
         stack.push(root);
        //错 不应命名为cur，应该命名为"应该判断"
        TreeNode shouldJudge = root.left;

        while(!stack.isEmpty()){
            //1 左到底
            if(shouldJudge != null){
                //错 stack.push(shouldJudge.left); 应去掉left
                stack.push(shouldJudge);
                shouldJudge = shouldJudge.left;
            }
            //2 当前自定义的nextNode（可能是左/右）空
            else {
                //3 pop res
                TreeNode top = stack.pop();
                res.add(top.val);
                //3.1 判断是否 右1 （之后shouldJudge仍继续左）
                if(top.right != null){
                    //4 右1 存入q 之后继续左
                    TreeNode thisNode = top.right;
                    stack.push(thisNode);
                    shouldJudge = thisNode.left;
                }
            }
        }
        return res;
    }

    @Test
    public void test(){
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        inorderTraversal(t1);
        System.out.println(res);
    }
}
